package top.saiyin.list;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Program: leetcode
 * @Description: 两数之和
 * @Author: sy
 * @Create: 2020-08-24
 **/
public class IntersectionOfTwoArrays {

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 1};
        int[] nums2 = {2, 2};
        int[] intersect = intersect2(nums1, nums2);
        for (int i = 0; i < intersect.length; i++) {
            System.out.print(intersect[i] + ",");
        }
    }

    public static int[] intersect(int[] nums1, int[] nums2) {

        // 降低空间复杂度
        if (nums1.length > nums2.length) {
            intersect(nums2, nums1);
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            // 当Map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue
            int count = map.getOrDefault(i, 0) + 1;
            map.put(i, count);
        }

        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        // 将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。
        // 注意这里包括下标from，不包括上标to。
        return Arrays.copyOfRange(intersection, 0, index);
    }


    public static int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        // 定义两个头指针，和一个临时指针
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            // 如果两个数字不相等，则将指向较小数字的指针右移一位，
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
                // 如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。
            } else {
                intersection[index] = nums1[index1];
                index++;
                index1++;
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
